#define _CRT_SECURE_NO_WARNINGS  1

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"Queue.h"

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

BTNode* CreatTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);


	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node6->left = node7;

	return node1;
}

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);

}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PreOrder(root->left);
	printf("%d ", root->data);
	PreOrder(root->right);

}

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PreOrder(root->left);
	PreOrder(root->right);
	printf("%d ", root->data);

}

int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : 
		TreeSize(root->left) 
		+TreeSize(root->right)  
		+1;
}

int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;

	int left = TreeHeight(root->left);
	int right = TreeHeight(root->right);

	return left > right ? left + 1 : right + 1;
}

int TreeKlevel(BTNode* root,int k)
{
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	int left = TreeKlevel(root->left, k - 1);
	int right = TreeKlevel(root->right, k - 1);

	return left + right ;
}

BTNode* BTFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;

	BTNode* left = BTFind(root->left, x);
	if (left)
		return left;

	BTNode* right = BTFind(root->right, x);
	if (right)
		return right;

	return NULL;
}

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);

		if (front->left)
			QueuePush(&q, front->left);

		if (front->right)
			QueuePush(&q, front->right);
	}

	QueueDestroy(&q);
}

int main()
{
	BTNode* root = CreatTree();


	PreOrder(root);
	printf("\n");

	InOrder(root);
	printf("\n");

	PostOrder(root);
	printf("\n");

	printf("Size=%d",TreeSize(root));
	printf("\n");

	printf("Height=%d",TreeHeight(root));
	printf("\n");

	printf("TreeKlevel=%d", TreeKlevel(root, 4));
	printf("\n");

	printf("%p",BTFind(root, 7));
	printf("\n");

	LevelOrder(root);

	return 0;
}